﻿/**************************************************************
 * 
 * Copyright © Dmitry Kukushkin <codecity@gmail.com> 2007
 * All Rights Reserved
 * 
 **************************************************************/

using System;
using WebMoney.SignerFX;

namespace WebMoney.Cryptography
{
    /// <summary>
    /// Вычисление степени натурального числа по модулю. Быстрый бинарный алгоритм.
    /// Существует объектно-ориентированная реализация данного алгоритма. Более наглядная, но проигрывает в скорости.
    /// </summary>
    internal sealed class ModExp
    {
        private const int BYTES = 4; // количество байт в типе исользуемом для вычислений
        private const int BITS = 32; // количество бит в типе исользуемом для вычислений
        private const uint BIT_MASK = 0x80000000; // битовая маска
        private const int USHORT_BYTES = 2;

        private uint[][] modulusShift; // модуль, сдвинутый побитно
        private uint[][] multiplicandShift; // множимое, сдвинутое побитно

        /// <summary>
        /// Создание объекта
        /// </summary>
        public ModExp()
        {
            modulusShift = new uint[BITS + 1][];
            multiplicandShift = new uint[BITS][];
        }

        /// <summary>
        /// Инициализация класса для повторного использования
        /// </summary>
        public void Initialize()
        {
            Array.Clear(modulusShift, 0, BITS + 1);
            Array.Clear(multiplicandShift, 0, BITS);
        }

        // Побитовый сдвиг влево
        private static void rotateLeft(ref uint[] value)
        {
            byte carry = 0;

            for (int pos = 0; pos < value.Length; pos++)
            {
                byte nextCarry;

                // Если последний бит 1
                nextCarry = (0 != (value[pos] & BIT_MASK)) ? (byte)1 : (byte)0;

                value[pos] <<= 1;

                value[pos] |= carry;

                carry = nextCarry;
            }

            // Расширение массива
            if (1 == carry)
            {
                Array.Resize(ref value, value.Length + 1);
                value[value.Length - 1] = 1;
            }
        }

        // Создание копии объекта uint[]
        private static uint[] CloneUint32(uint[] value)
        {
            uint[] result = new uint[value.Length];
            value.CopyTo(result, 0);

            return result;
        }

        // Сдвигаем побитово модуль
        private void shiftModulus(uint[] modulus)
        {
            modulusShift[0] = CloneUint32(modulus);

            for (int pos = 1; pos < BITS + 1; pos++)
            {
                modulusShift[pos] = CloneUint32(modulusShift[pos - 1]);
                rotateLeft(ref modulusShift[pos]);
            }
        }

        // Сдвигаем побитово множимое
        private void shiftMultiplicand(uint[] multiplicand)
        {
            multiplicandShift[0] = CloneUint32(multiplicand);

            for (int pos = 1; pos < BITS; pos++)
            {
                multiplicandShift[pos] = CloneUint32(multiplicandShift[pos - 1]);
                rotateLeft(ref multiplicandShift[pos]);
            }
        }

        // Количество значащих элементов в массиве uint
        private static int significance(uint[] value)
        {
            for (int pos = value.Length - 1; pos >= 0; pos--)
                if (0 != value[pos])
                    return pos + 1; // длина больше позиции на единицу

            return 0;
        }

        // Количество значащих элементов в массиве ushort
        private static int significance(ushort[] value)
        {
            for (int pos = value.Length - 1; pos >= 0; pos--)
                if (0 != value[pos])
                    return pos + 1; // длина больше позиции на единицу

            return 0;
        }

        //// Количество значащих элементов в массиве byte
        //private static int significance(byte[] value)
        //{
        //    for (int pos = value.Length - 1; pos >= 0; pos--)
        //        if (0 != value[pos])
        //            return pos + 1; // длина больше позиции на единицу

        //    return 0;
        //}

        // Cравнение двух массивов uint
        private static sbyte compare(uint[] lhs, uint[] rhs)
        {
            for (int pos = Math.Max(lhs.Length, rhs.Length) - 1; pos >= 0; pos--)
            {
                if (((lhs.Length > pos) ? lhs[pos] : 0) < ((rhs.Length > pos) ? rhs[pos] : 0))
                    return -1;
                else if (((lhs.Length > pos) ? lhs[pos] : 0) > ((rhs.Length > pos) ? rhs[pos] : 0))
                    return 1;
            }

            return 0;
        }

        // Сложение
        private static void add(ref uint[] lhs, uint[] rhs)
        {
            if (lhs.Length < significance(rhs))
                Array.Resize(ref lhs, significance(rhs));

            int carry = 0;

            for (int pos = 0; pos < lhs.Length; pos++)
            {
                ulong temp = (ulong)lhs[pos] + ((rhs.Length > pos) ? rhs[pos] : 0) + (ulong)carry;
                lhs[pos] = unchecked((uint)temp);
                carry = ((temp & (1UL << BITS)) != 0) ? 1 : 0;
            }

            // расширение массива
            if (1 == carry)
            {
                Array.Resize(ref lhs, lhs.Length + 1);
                lhs[lhs.Length - 1] = 1;
            }
        }

        // Вычитание (lhs >= rhs)
        private static void sub(ref uint[] lhs, uint[] rhs)
        {
            if (lhs.Length < significance(rhs))
                throw new ArithmeticException("lhs < rhs");

            int borrow = 0;

            for (int pos = 0; pos < lhs.Length; pos++)
            {
                ulong temp = (ulong)lhs[pos] - ((rhs.Length > pos) ? rhs[pos] : 0) - (ulong)borrow;
                lhs[pos] = unchecked((uint)temp);
                borrow = (((temp & (1UL << BITS)) != 0) ? 1 : 0);
            }

            if (1 == borrow)
                throw new ArithmeticException("borrow");
        }

        // Умножение по модулю
        private uint[] modMult(uint[] multiplicand, uint[] multiplier)
        {
            uint[] result = new uint[multiplicand.Length];

            shiftMultiplicand(multiplicand);

            for (int mulPos = significance(multiplier) - 1; mulPos >= 0; mulPos--)
            {
                if (0 != result[result.Length - 1])
                    Array.Resize(ref result, result.Length + 1);

                for (int pos = result.Length - 1; pos > 0; pos--)
                    result[pos] = result[pos - 1];

                result[0] = 0;

                // Умножение
                for (int pos = BITS - 1; pos >= 0; pos--)
                    if ((multiplier[mulPos] & ((uint)1 << pos)) != 0)
                        add(ref result, multiplicandShift[pos]);

                // Нахождение остатка
                for (int pos = BITS; pos >= 0; pos--)
                    if (compare(result, modulusShift[pos]) >= 0)
                        sub(ref result, modulusShift[pos]);
            }

            return result;
        }

        ///// <summary>
        ///// Возведение в степень по модулю
        ///// </summary>
        ///// <param name="value">Значение</param>
        ///// <param name="exponent">Степень</param>
        ///// <param name="modulus">Модуль</param>
        ///// <returns>Результат</returns>
        //public byte[] GetResult(byte[] value, byte[] exponent, byte[] modulus)
        //{
        //    uint[] uValue = new uint[(value.Length + BYTES - 1) / BYTES];
        //    uint[] uExponent = new uint[(exponent.Length + BYTES - 1) / BYTES];
        //    uint[] uModulus = new uint[(modulus.Length + BYTES - 1) / BYTES];

        //    Buffer.BlockCopy(value, 0, uValue, 0, value.Length);
        //    Buffer.BlockCopy(exponent, 0, uExponent, 0, exponent.Length);
        //    Buffer.BlockCopy(modulus, 0, uModulus, 0, modulus.Length);

        //    return GetResult(uValue, uExponent, uModulus);
        //}

        ///// <summary>
        ///// Возведение в степень по модулю
        ///// </summary>
        ///// <param name="value">Значение</param>
        ///// <param name="exponent">Степень</param>
        ///// <param name="modulus">Модуль</param>
        ///// <returns>Результат</returns>
        //public byte[] GetResult(uint[] value, uint[] exponent, uint[] modulus)
        //{
        //    uint[] temp = GetUInt32Result(value, exponent, modulus);
        //    byte[] result = new byte[temp.Length * BYTES];
        //    Buffer.BlockCopy(temp, 0, result, 0, temp.Length * BYTES);

        //    if (result.Length != significance(result))
        //        Array.Resize(ref result, significance(result));

        //    return result;
        //}

        /// <summary>
        /// Возведение в степень по модулю
        /// </summary>
        /// <param name="value">Значение</param>
        /// <param name="exponent">Степень</param>
        /// <param name="modulus">Модуль</param>
        /// <returns>Результат</returns>
        public ushort[] GetUint16Result(uint[] value, uint[] exponent, uint[] modulus)
        {
            uint[] temp = GetUInt32Result(value, exponent, modulus);
            ushort[] result = new ushort[temp.Length * BYTES / USHORT_BYTES];
            Buffer.BlockCopy(temp, 0, result, 0, temp.Length * BYTES);

            if (result.Length != significance(result))
                Array.Resize(ref result, significance(result));

            return result;
        }

        /// <summary>
        /// Возведение в степень по модулю
        /// </summary>
        /// <param name="value">Значение</param>
        /// <param name="exponent">Степень</param>
        /// <param name="modulus">Модуль</param>
        /// <returns>Результат</returns>
        public uint[] GetUInt32Result(uint[] value, uint[] exponent, uint[] modulus)
        {
            // ***** Проверка аргументов *****

            if (null == value)
                throw new ArgumentNullException("value");

            if (null == exponent)
                throw new ArgumentNullException("exponent");

            if (null == modulus)
                throw new ArgumentNullException("modulus");

            if (0 == value.Length)
                throw new ArgumentOutOfRangeException("value");

            if (0 == exponent.Length)
                throw new ArgumentOutOfRangeException("exponent");

            if ((0 == modulus.Length) || ((1 == modulus.Length) && (0 == modulus[0])))
                throw new ArgumentOutOfRangeException("modulus");

            // ***** Уникальные ситуации *****

            if (1 == value.Length && 0 == value[0])
                return new uint[] { 0 };

            if (1 == modulus.Length && 1 == modulus[0])
                return new uint[] { 0 };

            if (1 == exponent.Length && 0 == exponent[0])
                return new uint[] { 1 };

            shiftModulus(modulus);

            uint[] result = new uint[] { 1 }; // переменная для реультата вычислений

            int expLen = significance(exponent); // значащая длина exponent
            int expBits = expLen * BITS; // количество битов степени
            int expPos = expLen - 1; // позиция
            uint bitMask = BIT_MASK; // битовая маска

            // Узнаем количество значащих битов степени
            while (0 == (exponent[expPos] & bitMask))
            {
                bitMask >>= 1;
                expBits--;
            }

            // Возведение числа в натуральную степень по модулю
            while (expBits != 0)
            {
                result = modMult(result, result);

                if (0 != (exponent[expPos] & bitMask)) // если бит равен 1
                    result = modMult(result, value);

                expBits--;
                bitMask >>= 1;

                if (0 == bitMask)
                {
                    bitMask = BIT_MASK;
                    expPos--;
                }
            }

            if (significance(result) != result.Length)
                Array.Resize(ref result, significance(result));

            return result;
        }
    }

    internal sealed class ModExp2
    {
        private const int BITS = 32;

        private ExtendedUInt32Array[] modulusShift;
        private ExtendedUInt32Array[] multiplicandShift;

        private ModExp2()
        {
            modulusShift = new ExtendedUInt32Array[BITS + 1];
            multiplicandShift = new ExtendedUInt32Array[BITS];
        }

        public void Initialize()
        {
            Array.Clear(modulusShift, 0, BITS + 1);
            Array.Clear(multiplicandShift, 0, BITS);
        }

        private void shiftModulus(ExtendedUInt32Array modulus)
        {
            modulusShift[0] = modulus.Clone();

            for (int pos = 1; pos < BITS + 1; pos++)
            {
                modulusShift[pos] = modulusShift[pos - 1].Clone();
                modulusShift[pos] = modulusShift[pos] << 1;
            }
        }

        private void shiftMultiplicand(ExtendedUInt32Array multiplicand)
        {
            multiplicandShift[0] = multiplicand.Clone();

            for (int pos = 1; pos < BITS; pos++)
            {
                multiplicandShift[pos] = multiplicandShift[pos - 1].Clone();
                multiplicandShift[pos] = multiplicandShift[pos] << 1;
            }
        }

        private ExtendedUInt32Array modMult(ExtendedUInt32Array multiplicand, ExtendedUInt32Array multiplier)
        {
            ExtendedUInt32Array result = new ExtendedUInt32Array();

            shiftMultiplicand(multiplicand);

            for (int mulPos = multiplier.Length - 1; mulPos >= 0; mulPos--)
            {
                result = result << BITS;

                for (int pos = BITS - 1; pos >= 0; pos--)
                    if (multiplier[mulPos][pos])
                        result = result + multiplicandShift[pos];

                for (int pos = BITS; pos >= 0; pos--)
                    if (result >= modulusShift[pos])
                        result = result - modulusShift[pos];
            }

            return result;
        }

        internal ExtendedUInt32Array GetResult(ExtendedUInt32Array value, ExtendedUInt32Array exponent, ExtendedUInt32Array modulus)
        {
            if (null == value)
                throw new ArgumentNullException("value");

            if (null == exponent)
                throw new ArgumentNullException("exponent");

            if (null == modulus)
                throw new ArgumentNullException("modulus");

            if (0 == value.Length)
                throw new ArgumentOutOfRangeException("value");

            if (0 == exponent.Length)
                throw new ArgumentOutOfRangeException("exponent");

            if ((0 == modulus.Length) || ((1 == modulus.Length) && (0 == modulus[0])))
                throw new ArgumentOutOfRangeException("modulus");

            if (1 == value.Length && 0 == value[0])
                return new uint[] { 0 };

            if (1 == modulus.Length && 1 == modulus[0])
                return new uint[] { 0 };

            if (1 == exponent.Length && 0 == exponent[0])
                return new uint[] { 1 };

            shiftModulus(modulus);

            ExtendedUInt32Array result = new ExtendedUInt32Array(new ExtendedUInt32[] { 1 }); // реультат вычислений
            int expBit = exponent.BitsCount;

            while (expBit != 0)
            {
                result = modMult(result, result);

                if (exponent[expBit / BITS][expBit % BITS - 1]) // если бит равен 1
                    result = modMult(result, value);

                expBit--;
            }

            return result;
        }
    }
}